Route planning devices (often referred to as Satellite Nav.'s, Portable Navigation Devices (PND's) or similar) together with web sites such as routes.tomtom.com are well known and allow a user thereof to plan a route between two points. Such technology may be referred to generically as electronic route planning or just route planning.
Map data for such electronic route planning comes from specialist map vendors such as Tele Atlas NV. When performed on a PND such route planning typically uses location data from a GPS system. However, other applications may allow a user to input his/her location or other point to be considered for routing planning purposes.
Such map data comprises a plurality of roads (and other navigable paths) which can be described as lines—i.e. vectors or road segments (e.g. start point, end point, direction for a road, with an entire road being made up of many hundreds of such segments, each uniquely defined by start point/end point direction parameters). A map is then a set of such road vectors, data associated with each vector (speed limit; travel direction, etc.) plus points of interest (POIs), plus road names, plus other geographic features like park boundaries, river boundaries, etc., all of which are defined in terms of vectors. All map features (e.g. road vectors, POIs etc.) are typically defined in a co-ordinate system that corresponds with or relates to the GPS co-ordinate system, enabling a device's position as determined through a GPS system to be located onto the relevant road shown in a map and for an optimal route to be planned to a destination.
Such map data can be extensive. It is known for maps to cover areas having in excess of 120,000,000 vectors and an example of such map data would be a map covering the area of Europe and Russia. As such, planning a route using such map data is complex and can be time consuming. Also, it is known that such route planning is a trade-off between accuracy and time.
Prior art which has considered ideas at improving the speed at which routing can occur includes U.S. Pat. No. 6,636,800 which discusses refinements to the A* best-first search strategy suitable for much smaller map sizes such as the highway road network of Western Europe (having roughly 400,000 vectors).